package 链表;

/**
 * @Author zxl
 * @Date 2021/12/18 20:37
 * @Desc
 */
public class 反转链表 {

    /**
     * 初始化链表
     *
     * @return
     */
    public static Node initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        return node1;
    }

    /**
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
     *
     * @param args
     */
    public static void main(String[] args) {

        Node head = initData();
        System.out.println("反转前：" + head.toString());
        Node newHead = recursion3(head);
//        Node newHead = otherNode(head);
        System.out.println("反转后：" + newHead.toString());

    }


    /**
     * 双指针
     * @param head
     * @return
     */
    public Node twoIndexPoint(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node emptyNode = new Node();
        while (head.next != null) {
            Node temp = head.next;
            head.next = emptyNode;
            emptyNode = head;
            head = temp;
        }
        return emptyNode;

    }


    public Node recursion4(Node newHead) {
        // 临界条件
        if (newHead == null || newHead.next == null) {
            return newHead;
        }
        // 向后递归
        Node cur = recursion4(newHead.next);
        // 反转
        newHead.next.next = newHead;
        newHead.next = null;

        return cur;
    }


    public static Node recursion2(Node head) {

        Node emptyNode = new Node();
        Node tempHead = emptyNode;
        while (head != null) {
            Node temp = head.next;
            head.next = emptyNode;
            emptyNode = head;
            head = temp;
        }
        return emptyNode;

    }

    /**
     * 递归
     *
     * @param head
     * @return
     */
    public static Node recursion3(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node curr = recursion3(head.next);

        head.next.next = head;

        head.next = null;

        return curr;
    }


    /**
     * 2个指针
     *
     * @param head
     * @return
     */
    protected static Node otherNode(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node curr = head;
        while (curr != null) {
            // 保存失去引用的
            Node temp = curr.next;
            // 反转
            curr.next = pre;
            // 下次循环
            pre = curr;
            curr = temp;
        }

        return pre;


    }

    /**
     * 递归
     * 👇 找到尾节点
     * 👆 更改引用关系
     *
     * @param head 头节点
     * @return
     */
    protected static Node recursion(Node head) {
        // 临界条件
        if (head == null || head.next == null) {
            return head;
        }
        // 临界条件时候current=尾节点,每次递归返回current
        Node current = recursion(head.next);
        // 比如原链表：1->2->3->4
        // 第一次执行这行代码时，head是3，current是4
        // 这里用两个next反转3和4之间的关系
        head.next.next = head;
        // 虽然head的next会在上一层递归改掉
        // 但是当回到第一个节点1的时候，是没法改掉1->2，发生1和2中间产生双向指针，导致死循环
        // 所以这里必须将head的指向关系清掉
        head.next = null;
        // current就是反转后的头节点
        return current;
    }
}
